#include"Heap.h"

void HeapPrint(HP* php)
{
    assert(php);

    int i = 0;
    for(i = 0; i < php->size; i++)
    {
        printf("%d ", php->a[i]);
    }
    printf("\n");
}
void HeapInit(HP* php)
{
    assert(php);

    php->a = NULL;
    php->size = php->capacity = 0;
}
void HeapDestroy(HP* php)
{
    assert(php);

    free(php->a);
    php->a = NULL;
    php->capacity = php->size = 0;
}
void HeapSwap(HPDataType* x, HPDataType* y)
{
    HPDataType tmp = *x;
    *x = *y;
    *y = tmp;
}
void AdjustUP(HPDataType* a, int child)
{
    int parent = (child - 1) / 2;

    while(child > 0)
    {
        if(a[child] < a[parent])
        {
           HeapSwap(&a[child], &a[parent]);

            child = parent;
            parent = (child - 1) / 2;
        }
        else{
            break;
        }
    }

}

void HeapPush(HP* php, HPDataType x)
{
    assert(php);
    
    if(php->capacity == php->size)
    {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)* newcapacity);
        if(tmp == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        php->a = tmp;
        php->capacity = newcapacity;
    }

    php->a[php->size] = x;
    php->size++;

    AdjustUP(php->a, php->size - 1);

}
void AdjustDown(HPDataType* a, int size, int parent)
{
    int child = parent * 2 + 1;
  //  if(a[child + 1] < a[child] && child + 1 < size)
  //  {
  //      child = child + 1;
  //  }
    
    while(child < size)
    {
            if(a[child + 1] < a[child] && child + 1 < size)
            {
                  child = child + 1;
            }
        if(a[child] < a[parent])
        {
            HeapSwap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;

        }
        else{
            break;
        }
    }

}
void HeapPop(HP* php)
{
    assert(php);
    assert(php->size > 0);

    HeapSwap(&(php->a[0]), &(php->a[php->size - 1]));
    php->size--;

    AdjustDown(php->a, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
    assert(php);
    assert(php->size > 0);
    return php->a[0];
}
bool HeapEmpty(HP* php)
{
    assert(php);

    return php->size == 0;
}
int HeapSize(HP* php)
{
    assert(php);

    return php->size;
}
